package DataStr.homework02.h2;
public class ex01 {
    //1、假设以I和O分别表示进栈和出栈操作，栈的初态和终态均为空，
    // 进栈和出栈的操作序列str可表示为仅由I和O组成的字符串。设计一个算法判定str是否合法。
    private Node top;//栈顶元素的引入
    int size;
    //构造函数初始化
    public ex01(String s){
        top=null;
        size=0;
    }
    //节点类
    public static class Node{
        int value;//数据域
        Node next;//指针域
        //构造函数初始化
        public Node(int a){
            value=a;
            next=null;
        }
    }
    public void push(int a){
            Node newNode=new Node(a);//创建新节点
            newNode.next=top;//新节点的下一个指向原来的top
            top=newNode;//更新栈顶元素为新节点
            size++;
    }
    public void pop()throws Exception {
            if (top == null) {
                throw new Exception("栈为空");
            }
            top = top.next;//让栈顶元素指向原来的栈顶元素的下一个节点
            size--;
    }
    //检查序列是否合法
    public boolean checkout(String s){
        //循环遍历，判断
        for (int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch=='I'){
                push(i);
            }else if (ch=='O'){
                try {
                    pop();
                }catch (Exception e){
                    System.out.println("该栈为空");
                    e.printStackTrace();
                }
            }else {
                return false;
            }
        }
        return size==0;
    }
    public static void main(String[]args) throws Exception {
        String a="IIIOOO";
        ex01 a1=new ex01(a);
        if(a1.checkout(a)){
            System.out.println("该栈合法");
        }else
            System.out.println("该栈非法");
    }
}
